<!DOCTYPE HTML>
<html lang="zh-CN">




<head>
    <meta charset="utf-8">
    <meta name="keywords" content="操作系统第二章, 深度学习 故障诊断 Java">
    <meta name="description" content="河海大学 | 计算机与信息学院 | 信号与信息处理">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <!-- Global site tag (gtag.js) - Google Analytics -->


    <title>操作系统第二章 | 世庆的博客</title>
    <link rel="icon" type="image/png" href="/shiqing/favicon.png">

    <link rel="stylesheet" type="text/css" href="/shiqing/libs/awesome/css/all.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/libs/materialize/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/css/my.css">

    <script src="/shiqing/libs/jquery/jquery.min.js"></script>

    <script src="https://sdk.jinrishici.com/v2/browser/jinrishici.js" charset="utf-8"></script>
<meta name="generator" content="Hexo 6.3.0"></head>




    <body>
        <header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="/shiqing/" class="waves-effect waves-light">
                    
                    <img src="/shiqing/medias/logo.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">世庆的博客</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fas fa-bars"></i></a>
<ul class="right nav-menu">
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/" class="waves-effect waves-light">
      
      <i class="fas fa-home" style="zoom: 0.6;"></i>
      
      <span>首页</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/tags" class="waves-effect waves-light">
      
      <i class="fas fa-tags" style="zoom: 0.6;"></i>
      
      <span>标签</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/categories" class="waves-effect waves-light">
      
      <i class="fas fa-bookmark" style="zoom: 0.6;"></i>
      
      <span>分类</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/archives" class="waves-effect waves-light">
      
      <i class="fas fa-archive" style="zoom: 0.6;"></i>
      
      <span>归档</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/about" class="waves-effect waves-light">
      
      <i class="fas fa-user-circle" style="zoom: 0.6;"></i>
      
      <span>关于</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/contact" class="waves-effect waves-light">
      
      <i class="fas fa-comments" style="zoom: 0.6;"></i>
      
      <span>留言板</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/friends" class="waves-effect waves-light">
      
      <i class="fas fa-address-book" style="zoom: 0.6;"></i>
      
      <span>友情链接</span>
    </a>
    
  </li>
  
  <li>
    <a href="#searchModal" class="modal-trigger waves-effect waves-light">
      <i id="searchIcon" class="fas fa-search" title="搜索" style="zoom: 0.85;"></i>
    </a>
  </li>
</ul>


<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="/shiqing/medias/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">世庆的博客</div>
        <div class="logo-desc">
            
            河海大学 | 计算机与信息学院 | 信号与信息处理
            
        </div>
    </div>

    

    <ul class="menu-list mobile-menu-list">
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-home"></i>
			
			首页
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/tags" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-tags"></i>
			
			标签
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/categories" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-bookmark"></i>
			
			分类
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/archives" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-archive"></i>
			
			归档
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/about" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-user-circle"></i>
			
			关于
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/contact" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-comments"></i>
			
			留言板
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/friends" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-address-book"></i>
			
			友情链接
		</a>
          
        </li>
        
        
        <li><div class="divider"></div></li>
        <li>
            <a href="https://github.com/sqtian-hhu/" class="waves-effect waves-light" target="_blank">
                <i class="fab fa-github-square fa-fw"></i>Fork Me
            </a>
        </li>
        
    </ul>
</div>


        </div>

        
            <style>
    .nav-transparent .github-corner {
        display: none !important;
    }

    .github-corner {
        position: absolute;
        z-index: 10;
        top: 0;
        right: 0;
        border: 0;
        transform: scale(1.1);
    }

    .github-corner svg {
        color: #0f9d58;
        fill: #fff;
        height: 64px;
        width: 64px;
    }

    .github-corner:hover .octo-arm {
        animation: a 0.56s ease-in-out;
    }

    .github-corner .octo-arm {
        animation: none;
    }

    @keyframes a {
        0%,
        to {
            transform: rotate(0);
        }
        20%,
        60% {
            transform: rotate(-25deg);
        }
        40%,
        80% {
            transform: rotate(10deg);
        }
    }
</style>

<a href="https://github.com/sqtian-hhu/" class="github-corner tooltipped hide-on-med-and-down" target="_blank"
   data-tooltip="Fork Me" data-position="left" data-delay="50">
    <svg viewBox="0 0 250 250" aria-hidden="true">
        <path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path>
        <path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2"
              fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path>
        <path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z"
              fill="currentColor" class="octo-body"></path>
    </svg>
</a>
        
    </nav>

</header>

        



<div class="bg-cover pd-header post-cover" style="background-image: url('/shiqing/medias/featureimages/19.jpg')">
    <div class="container" style="right: 0px;left: 0px;">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <h1 class="description center-align post-title">操作系统第二章</h1>
                </div>
            </div>
        </div>
    </div>
</div>




<main class="post-container content">

    
    <link rel="stylesheet" href="/shiqing/libs/tocbot/tocbot.css">
<style>
    #articleContent h1::before,
    #articleContent h2::before,
    #articleContent h3::before,
    #articleContent h4::before,
    #articleContent h5::before,
    #articleContent h6::before {
        display: block;
        content: " ";
        height: 100px;
        margin-top: -100px;
        visibility: hidden;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        width: 345px;
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        padding: 35px 0 15px 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content {
        padding-bottom: 30px;
        overflow: auto;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;

        position: absolute;
        right: 23.5vw;
        display: block;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #floating-toc-btn {
        position: fixed;
        right: 15px;
        bottom: 76px;
        padding-top: 15px;
        margin-bottom: 0;
        z-index: 998;
    }

    #floating-toc-btn .btn-floating {
        width: 48px;
        height: 48px;
    }

    #floating-toc-btn .btn-floating i {
        line-height: 48px;
        font-size: 1.4rem;
    }
</style>
<div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                            <a href="/shiqing/tags/%E8%BF%9B%E7%A8%8B/">
                                <span class="chip bg-color">进程</span>
                            </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                    <div class="post-cate">
                        <i class="fas fa-bookmark fa-fw icon-category"></i>
                        
                            <a href="/shiqing/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" class="post-category">
                                操作系统
                            </a>
                        
                    </div>
                    
                </div>
            </div>

            <div class="post-info">
                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-minus fa-fw"></i>发布日期:&nbsp;&nbsp;
                    2021-05-10
                </div>
                

                

                

                

                
            </div>
        </div>
        <hr class="clearfix">

        
        <!-- 是否加载使用自带的 prismjs. -->
        <link rel="stylesheet" href="/shiqing/libs/prism/prism.css">
        

        

        <div class="card-content article-card-content">
            <div id="articleContent">
                <h2 id="第二章"><a href="#第二章" class="headerlink" title="第二章"></a>第二章</h2><h3 id="进程"><a href="#进程" class="headerlink" title="进程"></a>进程</h3><p>程序：就是一个指令序列<br>进程：程序的一次执行过程</p>
<p>单道程序<br>程序的代码放在程序段内，程序运行过程处理的数据放在数据段内</p>
<p>多道程序技术：多道程序并发执行<br>系统为每个运行的程序配置一个数据结构，称为进程控制块（PCB）<br>用来存放进程描述信息，进程控制和管理信息，资源分配清单，处理机相关信息</p>
<p>PCB，程序段，数据段三部分构成了进程实体<br>所谓创建进程，实质上就是创建进程实体中的PCB；而撤销进程实质上是撤销进程实体中的PCB</p>
<p>PCB是进程存在的唯一标志</p>
<p>进程的组织方式：<br>链接方式：按照进程状态将PCB分为多个队列，操作系统持有指向各个队列的指针<br>执行指针指向当前处于运行态的指针<br>就绪队列指针指向就绪队列的队首，通常把优先级较高的放在队首<br>阻塞队列指向处于阻塞态的进程</p>
<p>索引方式：根据进程状态不同，建立几张索引表，操作系统持有指向各个索引表的指针<br>执行指针指向当前处于运行态的指针<br>就绪表<br>阻塞表</p>
<h3 id="进程的状态"><a href="#进程的状态" class="headerlink" title="进程的状态"></a>进程的状态</h3><p>运行状态，就绪状态，阻塞状态，创建状态，终止状态</p>
<p>三种基本状态<br>运行态：占有CPU，并在CPU上运行<br>就绪态：拥有了除处理机之外所有需要的资源，但由于没有空闲CPU，暂时不能运行一旦获得处理机即可立即进入运行态<br>阻塞态：等待操作系统分配资源</p>
<p>进程状态间的转换<br>创建态-&gt;就绪态<br>就绪态&lt;-&gt;运行态 进程被调度进入运行态,时间片到了或处理机被抢占返回就绪态<br>运行态-&gt;阻塞态 进程用系统调用的方式申请某种系统资源,或请求某件事情发生(主动) 进入阻塞态<br>阻塞态-&gt;就绪态 申请的资源被分配,或者等待的事件发生,进入就绪态<br>运行态-&gt;终止态 进程运行结束或运行过程遇到不可修复的错误</p>
<h3 id="进程控制"><a href="#进程控制" class="headerlink" title="进程控制"></a>进程控制</h3><p>进程控制的主要功能是对系统中的所有进程实施有效的管理,它具有创建新进程,撤销已有进程,实现进程状态转换等功能</p>
<p>状态转换时需修改PCB内容和相应队列防止内容与队列不一致发生错误,使用原语实现进程控制</p>
<p>原语特点: 不允许终端</p>
<p>关中断指令<br>原语代码<br>开中断指令</p>
<h3 id="进程通信"><a href="#进程通信" class="headerlink" title="进程通信"></a>进程通信</h3><p>指进程之间的信息交换<br>进程是分配系统资源的单位,因此各进程拥有的内存地址空间相互独立</p>
<p>为了保证安全,一个进程不能直接访问另一个进程的地址空间.<br>但是进程之间的信息交换又是必须实现的. 为了保证进程间的安全通信,操作系统提供了一些方法</p>
<p>共享存储<br>    操作系统为进程分配共享空间<br>    两个进程对共享空间互斥访问<br>    1. 基于数据结构的共享: 比如共享空间里只能放一个长度为10的数组,<br>        这种方式速度慢,限制多,是一种低级通信方式<br>    2. 基于存储区的共享: 在内存中画出一块共享存储区,数据的形式,存放位置都由进程控制,而不是操作系统<br>        相比之下更快,是一种高级通信方式</p>
<p>管道通信<br>    管道是指用于连接读写进程的一个共享文件,实际上就是在内存中开辟一个大小固定的缓冲区<br>    进程1写数据到管道,进程2从管道读数据<br>    1没写满2不能读,2没读空1不能写<br>    各进程互斥访问</p>
<pre><code>管道只能采用半双工通信,要实现双向通信,需要设置两个管道
    
</code></pre>
<p>消息传递<br>    进程间的数据交换以格式化的消息为单位. 进程通过操作系统提供的发送消息&#x2F;接收消息两个原语进行数据交换<br>    1. 直接通信方式<br>        进程通过发送原语创建消息,消息直接挂到接受进程的消息缓冲队列上,接受进程通过接收原语依次读取消息<br>    2. 间接通信方式<br>        消息要先发送到中间实体(信箱)中,系统管理这些消息,具体是哪些进程发,哪些进程收都写在消息头里</p>
<h3 id="线程"><a href="#线程" class="headerlink" title="线程"></a>线程</h3><p>有的进程可能需要同时做很多事，而传统的进程只能串行地执行一系列程序。<br>为此引入线程来增加并发度<br>引入线程后，线程成了程序执行流的最小单位</p>
<p>线程的属性：<br>线程是处理机调度的单位，进程是资源分配的单位<br>多CPU计算机中，各个线程占用不同的cpu<br>每个线程都有一个线程ID，线程控制块（TCB）<br>线程也有就绪，阻塞，运行三种基本状态<br>线程几乎不拥有系统资源<br>同一进程的不同线程间共享进程的资源<br>由于共享内存地址空间，同一进程的线程间通信甚至无需系统干预<br>同一进程中的线程切换，不会引起进程切换，系统开销小<br>不同进程中的线程切换，会引起进程切换，系统开销大</p>
<p>线程的实现方式<br>用户级线程：从用户角度看的线程<br>内核级线程：从操作系统视角看的线程，内核级线程才是处理机分配的单位</p>
<h3 id="处理机调度"><a href="#处理机调度" class="headerlink" title="处理机调度"></a>处理机调度</h3><p>从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现并发</p>
<p>作业调度：<br>    高级调度，按一定的原则从外存上处于后备队列的作业中挑选一个或多个作业，给他们分配内存等必要资源<br>    并建立相应的进程（建立PCB），以使他们获得竞争处理机的权利。</p>
<pre><code>高级调度是外存与内存之间的调度，每个作业只调入一次，调出一次，调入时PCB创建，调出时PCB撤销
</code></pre>
<p>内存调度：<br>    中极调度，引入虚拟存储技术后，可将暂时不能运行的进程调至外存等待。<br>    等他重新具备运行条件且内存又稍有空闲时，再重新调入内存<br>    提高内存利用率和系统吞吐量<br>    暂时调出的进程状态为挂起状态，PCB并不会一起调出</p>
<p>挂起与阻塞的区别：两种状态都是暂不能获得CPU的服务<br>    但挂起态将进程映像调到外存去，阻塞态进程映像还在内存中</p>
<p>进程调度：<br>    低级调度，从就绪队列中选取一个进程，将处理机分配给他<br>    是操作系统中最基本的一种调度</p>
<h3 id="进程调度与进程切换的区别"><a href="#进程调度与进程切换的区别" class="headerlink" title="进程调度与进程切换的区别"></a>进程调度与进程切换的区别</h3><p>狭义的进程调度指的是从就绪队列中选中一个要运行的进程。<br>这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况需要进程切换<br>进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程</p>
<p>广义的进程调度包含了选择一个进程和进程切换两个步骤</p>
<p>进程切换的过程主要完成了<br>    1. 对原来运行进程各种数据的保存<br>    2. 对新的进程各种数据的恢复</p>
<p>进程切换是有代价的，因此如果过于频繁的进行进程调度，切换，必然使整个系统效率降低</p>
<h3 id="调度算法的评价指标"><a href="#调度算法的评价指标" class="headerlink" title="调度算法的评价指标"></a>调度算法的评价指标</h3><p>cpu利用率：指cpu忙碌的时间占总时间的比例<br>系统吞吐量：单位时间内完成作业的数量<br>周转时间：从作业提交给系统到作业完成为止的间隔&#x3D;作业完成时间-作业提交时间<br>    平均周转时间&#x3D;各作业周转时间之和&#x2F;作业数<br>    带权周转时间&#x3D;作业周转时间&#x2F;作业实际运行时间 （越小越好）<br>    平均带权周转时间&#x3D;各作业带权周转时间之和&#x2F;作业数</p>
<p>等待时间：进程&#x2F;作业处于等待处理机状态时间之和，时间越长，用户满意度越低</p>
<p>响应时间：从用户提交请求到首次产生响应所用的时间</p>
<h3 id="调度算法"><a href="#调度算法" class="headerlink" title="调度算法"></a>调度算法</h3><p>{<br>  先来先服务 FCFS<br>  短作业优先 SJF<br>  高响应比优先 HRRN<br>}</p>
<ol>
<li><p>先来先服务 First Come First Serve<br>算法思想： 主要从公平的角度考虑，类似于排队买东西<br>算法规则：按照作业&#x2F;进程到达的先后顺序进行服务<br>用于作业&#x2F;进程调度：用于作业调度时，考虑是哪个作业先到达后备队列<br>            用于进程调度时，考虑是哪个进程先到达就绪队列<br>是否可抢占：非抢占式算法<br>优缺点：<br> 优点：公平，算法实现简单<br> 缺点：排在长作业&#x2F;进程后面的短作业需要等待很长时间，带权周转时间很大，<br>   对短作业来说用户体验不好。即FCFS对长作业有利，对短作业不利<br>是否会导致饥饿：不会</p>
</li>
<li><p>短作业优先 Shortest Job First<br>算法思想：追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间<br>算法规则：最短作业&#x2F;进程优先得到服务，所谓最短，是指要求服务时间最短<br>用于作业&#x2F;进程调度：可用于作业调度也可用于进程调度，用于进程调度叫SPF，短进程优先<br>是否可抢占：SJF和SPF都是非抢占式，也有抢占式版本-最短剩余时间优先算法 SRTN<br>优缺点：<br> 优：“最短的”平均等待时间，平均周转时间<br> 缺：不公平，短作业有利，长作业不利<br>是否会导致饥饿：会，如果源源不断的短作业，可能使长作业饥饿，一直得不到会“饿死”</p>
<p> 最短剩余时间优先算法<br> 每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短<br> 则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度</p>
</li>
<li><p>高响应比优先 Highest Response Ratio Next<br>算法思想：要综合考虑作业&#x2F;进程的等待时间和要求服务的时间<br>算法规则：每次调度时先计算各个作业&#x2F;进程的响应比，选择响应比最高的作业为其服务<br>   响应比&#x3D;（等待时间+要求服务时间）&#x2F;要求服务时间<br>用于作业&#x2F;进程调度：可以用于作业调度也可以用于进程调度<br>是否可抢占：非抢占式的算法，只有当前运行的作业&#x2F;进程主动放弃处理机时，才需要调度，才需要计算响应比<br>优缺点：<br> 综合考虑了等待时间和运行时间（要求服务时间）<br> 等待时间相同时，要求服务时间短的优先（SJF的优点）<br> 要求服务时间相同时，等待时间长的优先（FCFS的优点）<br> 对于长作业优先来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题<br>是否会导致饥饿：不会</p>
</li>
</ol>
<p>这三种算法一般适合用于早期的批处理系统。</p>
<h3 id="适用于交互式系统的调度算法"><a href="#适用于交互式系统的调度算法" class="headerlink" title="适用于交互式系统的调度算法"></a>适用于交互式系统的调度算法</h3><p>时间片轮转轮转调度算法<br>优先级调度算法<br>多级反馈队列算法</p>
<ol>
<li>时间片轮转轮转调度算法 Round-Robin<br>算法思想：公平地，轮流地为各个进程服务，让每个进程在一定时间间隔内都能得到响应<br>算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程未在一个时间片内执行完，<br>   则剥夺处理机，将进程重新放到就绪队列队尾重新排队<br>用于作业&#x2F;进程调度：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）<br>是否可抢占：若进程未能在时间片内运行完，将被强行剥夺处理机使用权。属于抢占式算法<br>优缺点：<br> 优：公平，响应快，是用于分时操作系统<br> 缺：高频率的进程切换，因此会有一定开销，不区分任务紧急程度<br>是否会导致饥饿：不会</li>
</ol>
<p>如果时间片太大，使得每一个进程都能在一个时间片内就完成，则时间片轮转调度算法会退化为先来先服务算法<br>因此时间片不能太大<br>另一方面，进程调度，切换是有时间代价的，如果时间片太小，会导致进程切换过于频繁，系统会花大量时间来处理进程切换<br>因此时间片也不能太小</p>
<ol start="2">
<li>优先级调度算法<br>算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序<br>算法规则：每个作业&#x2F;进程有各自的优先级，调度时选择优先级最高的作业&#x2F;进程<br>用于作业&#x2F;进程调度：既可用于作业调度，也可用于进程调度。甚至还可用于I&#x2F;O调度<br>是否可抢占：抢占式，非抢占式都有。<br>优缺点：<br> 优：用优先级区分紧急程度，重要程度，是用于实时操作系统。可灵活地调整对各种作业&#x2F;进程的偏好程度<br> 缺：若源源不断地有高优先级的进程到来，则可能导致饥饿<br>是否会导致饥饿：会</li>
</ol>
<p>静态优先级：创建进程时确定，之后一直不变<br>动态优先级：创建进程时有一个初始值，之后会动态调整</p>
<ol start="3">
<li>多级反馈队列算法<br>折中</li>
</ol>
<p>算法思想：对其他调度算法的折中权衡<br>算法规则：<br>    1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大<br>    2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片<br>       若用完时间片进程还未结束，则进程进入下一级队列队尾，如果此时已经是最下级的队列<br>       则重新放回该队列队尾<br>    3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片<br>    被抢占处理机的进程重新放回原队列队尾，不会放入下一级</p>
<p>用于作业&#x2F;进程调度：用于进程调度<br>抢占：抢占式的算法。在k级队列的进程运行过程中，若更上级的队列中进入一个新进程，<br>      因此新进程会抢占处理机，原来运行的进程放回k级队列队尾<br>优缺点：集大成<br>是否会导致饥饿：会</p>
<h2 id="进程同步与互斥"><a href="#进程同步与互斥" class="headerlink" title="进程同步与互斥"></a>进程同步与互斥</h2><p>同步，亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，<br>这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系</p>
<p>我们把一个时间段内允许一个进程使用的资源称为临界资源<br>进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。</p>
<p>进程互斥的软件实现方法<br>单标志法<br>双标志先检查<br>双标志后检查<br>Peterson算法</p>
<ol>
<li>单标志法<br>算法思想：两个进程在访问完临界区后会把使用临界区的权限交给另一个进程<br>   也就是说，每个进程进入临界区的权限只能被另一个进程赋予</li>
</ol>
<p>主要问题：违背了空闲让进原则</p>
<ol start="2">
<li>双标志先检查法<br>算法思想：设置一个布尔型数组flag[]， 数组中各个元素用来标记各进程想进入临界区的意愿<br>比如flag[0]&#x3D;true意味着0号进程现在想要进入临界区。每个进程在进入临界区之前先检查当前<br>有没有别的进程想进临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。</li>
</ol>
<p>主要问题：违反忙则等待原则<br>while(flag[1]);<br>flag[0]&#x3D;true;<br>访问临界区</p>
<p>原因在于，进入区的检查和上锁两个处理不是一气呵成的。检查后，上锁前可能发生进程变换</p>
<ol start="3">
<li>双标志后检查<br>算法思想: 双标志位检查法的改版,前一个算法的问题是先检查,后上锁,但是这两个操作又无法一气呵成<br>因此导致了两个进程同时进入临界区的问题. 因此,人们又想到了先上锁后检查<br>flag[0]&#x3D;true;<br>while(flag[1]);<br>访问临界区</li>
</ol>
<p>主要问题: 虽然解决了忙则等待的问题，但是又违背了空闲让进和有限等待原则<br>会因各进程都长期无法访问临界资源而产生饥饿现象</p>
<ol start="4">
<li>Peterson算法<br>算法思想：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，<br>最后谁都无法进入临界区。如果双方都争着向进入临界区，那可以让进程尝试孔融让梨<br>主动让对方先使用临界区<br>boolean[] flag；表示进入临界区意愿的数组<br>int turn；表示优先让哪个进程进入临界区</li>
</ol>
<p>flag[0]&#x3D;true；<br>turn &#x3D;1；<br>while(flag[1]&amp;&amp;turn &#x3D; 1);<br>访问临界区</p>
<p>Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进，忙则等待，有限等待的原则。<br>但依然未遵循让权等待的原则</p>
<p>进程互斥的硬件实现方法</p>
<ol>
<li>中断屏蔽方法</li>
</ol>
<p>关中断<br>临界区<br>开中断 </p>
<p>利用开关中断指令实现，与原语的实现思想相同，即在某进程开始访问临界资源到结束访问为止不允许被中断<br>也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况</p>
<p>优点：简单、高效<br>缺点：不适用于多处理机：只适用于操作系统内核进程，不适用于用户进程（因为开关中断指令只能运行在内核态，<br>      这组指令如果让用户随意使用会很危险）</p>
<ol start="2">
<li><p>TestAndSet指令<br>简称TS指令或TSL指令<br>优点：实现简单，适用于多处理机环境<br>缺点：不满足让权等待</p>
</li>
<li><p>Swap指令</p>
</li>
</ol>
<p>信号量机制<br>信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），<br>可以用一个信号量来表示系统中某种资源的数量<br>比如：系统中只有一台打印机，就可以设置一个初值为1的信号量</p>
<p>用户可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥，进程同步 </p>
<p>一对原语：wait(S)和signal(S)<br>简称P,V操作,写作P(S),V(S)</p>
<p>信号量机制实现进程互斥</p>
<ol>
<li>分析并发进程的关键活动,划定临界区</li>
<li>设置互斥信号量(mutex),初值为1</li>
<li>在临界区之前执行P(mutex)</li>
<li>在临界区之后执行V(mutex)</li>
</ol>
<p>对不同的临界资源需要设置不同的互斥信号量</p>
<p>信号量机制实现同步</p>
<ol>
<li>分析什么地方需要实现”同步关系”,即必须保证”一前一后”执行的两个操作</li>
<li>设置同步信号量S,初始为0</li>
<li>在”前操作”之后执行V(S)</li>
<li>在”后操作”之前执行P(S)</li>
</ol>
<h3 id="经典进程互斥同步问题"><a href="#经典进程互斥同步问题" class="headerlink" title="经典进程互斥同步问题"></a>经典进程互斥同步问题</h3><h4 id="生产者-消费者问题"><a href="#生产者-消费者问题" class="headerlink" title="生产者-消费者问题"></a>生产者-消费者问题</h4><p>&#x2F;**</p>
<ul>
<li>系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用</li>
<li>生产者,消费者共享一个初始为空,大小为n的缓冲区</li>
<li>只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待</li>
<li>只有缓冲区不空时,消费者才能从中取出产品,否则必须等待</li>
<li></li>
<li>关系分析</li>
<li>同步关系: 缓冲区满时,生产者要等待消费者取走</li>
<li><pre><code>     缓冲区空时,消费者要等待生产者放入
</code></pre>
</li>
<li></li>
<li>互斥关系: 各进程必须互斥地访问</li>
<li></li>
<li>使用semaphore信号量实现<br> *&#x2F;</li>
</ul>
<p>生产者生产-v—full—p-&gt;消费者消费</p>
<p>生产者生产&lt;-p—empty—v-消费者消费</p>
<p>public class 生产者消费者 {<br>    private static Integer count &#x3D; 0;  &#x2F;&#x2F; 苹果数量<br>    &#x2F;&#x2F;创建三个信号量<br>    final Semaphore empty &#x3D; new Semaphore(5); &#x2F;&#x2F;同步信号量,表示缓冲区大小<br>    final Semaphore full &#x3D; new Semaphore(0); &#x2F;&#x2F; 同步信号量,表示产品的数量,即非空缓冲区的数量<br>    final Semaphore mutex &#x3D; new Semaphore(1);   &#x2F;&#x2F; 互斥信号量,实现对缓冲区互斥访问</p>
<pre><code>public static void main(String[] args) &#123;
    生产者消费者 test1 = new 生产者消费者();
    new Thread(test1.new Producer()).start();
    new Thread(test1.new Consumer()).start();

&#125;

// 生产者生产产品
class Producer implements Runnable &#123;
    @Override
    public void run() &#123;
        while(true) &#123;
            try &#123;
                empty.acquire(); //P(empty) 消耗一个空闲缓冲区
                mutex.acquire(); //P(mutex) 实现互斥是在同一进程中进行一对PV操作
                //把产品放入缓冲区
                Thread.sleep(400);
                count++;   // 每次生产一个产品,需要0.5秒

                System.out.println(Thread.currentThread().getName()
                        + &quot;生产者生产，目前总共有&quot; + count);
            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125; finally &#123;
                mutex.release();  //V(mutex) 互斥操作 解锁
                full.release();  // V(full) 增加一个产品
            &#125;
        &#125;
    &#125;
&#125;

//消费者消费产品
class Consumer implements Runnable &#123;
    @Override
    public void run() &#123;
        while(true) &#123;
            try &#123;
                full.acquire();  // P(full) 消耗一个产品
                mutex.acquire(); // P(mutex) 上锁

                Thread.sleep(100);
                count--;  // 每次消费一个产品,需要1s

                System.out.println(Thread.currentThread().getName()
                        + &quot;消费者消费，目前总共有&quot; + count);
            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125; finally &#123;
                mutex.release();  // V(mutex) 解锁
                empty.release();  // V(empty) 缓冲区多出一个空间
            &#125;
        &#125;
    &#125;
&#125;
</code></pre>
<p>}</p>
<p>通过在同一进程中进行一对P(mutex)v(mutex)操作实现互斥<br>如果P(mutex)操作在P(empty)前,<br>若此时缓冲区已经放满产品,则empty&#x3D;0,full&#x3D;n.<br>生产者先执行p(mutex)使mutex变为0,再执行p(empty),由于没有空闲缓冲区,因此生产者阻塞.<br>切回消费者进程<br>消费者进程执行p(mutex),由于mutex&#x3D;0,即生产者还没有释放对临界资源的锁,因此消费者也被阻塞<br>这就造成了生产者等待消费者释放空闲缓冲区,而消费者又等待生产者释放临界区的情况,出现死锁.</p>
<p>因此,实现互斥的P操作一定要在实现同步的P操作之后</p>
<h4 id="多生产者-多消费者问题"><a href="#多生产者-多消费者问题" class="headerlink" title="多生产者-多消费者问题"></a>多生产者-多消费者问题</h4><p>&#x2F;**</p>
<ul>
<li>桌子上有一直盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，</li>
<li>儿子专等着吃盘子里的橘子，女儿专等着吃盘子中的苹果。</li>
<li>只有盘子空时，爸爸或妈妈才可向盘子中放入一个水果。</li>
<li>仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取水果</li>
<li></li>
<li>关系分析</li>
<li>互斥关系: 对缓冲区(盘子)的访问要互斥地进行</li>
<li>同步关系: 1. 父亲将苹果放入盘子后,女儿才能取苹果</li>
<li><pre><code>      2. 母亲将橘子放入盘子后,儿子才能取橘子
</code></pre>
</li>
<li><pre><code>      3. 只有盘子空时,父亲或母亲才能放入水果
</code></pre>
</li>
<li>从”事件”的角度考虑,盘子变空事件在放入水果事件之前</li>
<li></li>
<li> *&#x2F;</li>
</ul>
<p>public class 多生产者多消费者 {</p>
<pre><code>final Semaphore mutex = new Semaphore(1);   //实现互斥访问盘子(缓冲区)
final Semaphore apple = new Semaphore(0);   //盘子中有几个苹果
final Semaphore orange = new Semaphore(0);  //盘子中有几个橘子
final Semaphore plate = new Semaphore(1);   //盘子中还可以放多少个水果



public static void main(String[] args) &#123;
    多生产者多消费者 test1 = new 多生产者多消费者();
    new Thread(test1.new dad()).start();
    new Thread(test1.new mom()).start();
    new Thread(test1.new daughter()).start();
    new Thread(test1.new son()).start();


&#125;


class dad implements Runnable&#123;

    @Override
    public void run() &#123;
        while(true)&#123;
            try &#123;

                System.out.println(&quot;爸爸正在削苹果&quot;);
                Thread.sleep(600);  //削一个苹果
                plate.acquire();  //P(plate)
                mutex.acquire();  //上锁

                Thread.sleep(100);  //把苹果放进盘子
                System.out.println(&quot;爸爸把苹果放进盘子了&quot;);
            &#125; catch (Exception e) &#123;
                e.printStackTrace();
            &#125;finally&#123;
                mutex.release();
                apple.release();
            &#125;
        &#125;
    &#125;
&#125;

class mom implements Runnable&#123;

    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;

                System.out.println(&quot;妈妈正在剥橘子&quot;);
                Thread.sleep(300);  //剥一个橘子
                plate.acquire();  //P(plate)
                mutex.acquire();  //P(mutex) 上锁

                Thread.sleep(100);  //把橘子放进盘子
                System.out.println(&quot;妈妈把橘子放进盘子了&quot;);
            &#125; catch (Exception e) &#123;
                e.printStackTrace();
            &#125;finally&#123;
                mutex.release();
                orange.release();
            &#125;
        &#125;
    &#125;
&#125;

class daughter implements Runnable&#123;


    @Override
    public void run() &#123;
        while (true)&#123;

            try &#123;
                apple.acquire();  //P(apple)
                mutex.acquire();  //P(mutex) 上锁
                Thread.sleep(100);  //从盘中取出苹果
                System.out.println(&quot;女儿取出了苹果&quot;);
            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                mutex.release();  //V(mutex)
                plate.release();  //V(plate)
                try &#123;
                    Thread.sleep(1000);  //吃掉苹果
                    System.out.println(&quot;女儿把苹果吃掉了&quot;);
                &#125; catch (InterruptedException e) &#123;
                    e.printStackTrace();
                &#125;

            &#125;

        &#125;
    &#125;
&#125;

class son implements Runnable&#123;
    @Override
    public void run() &#123;
        while (true)&#123;

            try &#123;
                orange.acquire();  //P(orange)
                mutex.acquire();  //P(mutex) 上锁
                Thread.sleep(100);  //从盘中取出橘子
                System.out.println(&quot;儿子取出了橘子&quot;);
            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                mutex.release();  //V(mutex) 解锁
                plate.release();  //V(plate)
                try &#123;
                    Thread.sleep(500);  //吃掉橘子
                    System.out.println(&quot;儿子把橘子吃掉了&quot;);
                &#125; catch (InterruptedException e) &#123;
                    e.printStackTrace();
                &#125;

            &#125;

        &#125;
    &#125;
&#125;
</code></pre>
<p>}</p>
<h4 id="吸烟者问题"><a href="#吸烟者问题" class="headerlink" title="吸烟者问题"></a>吸烟者问题</h4><p>&#x2F;**</p>
<ul>
<li>三个吸烟者和一个供应者进程. 每个吸烟者不停地卷烟并抽掉他,但是要卷起并抽掉,抽烟者需要有三种材料:烟草,纸和胶水</li>
<li>三个抽烟者中,第一个拥有烟草,第二个拥有纸,第三个拥有胶水.</li>
<li>供应者进程无限提供三种材料,供应者每次将两种材料放桌子上,拥有剩下材料的抽烟者取走抽烟,并给供应者一个信号完成了,</li>
<li>供应者就会把另外两种材料放桌子上,让三个抽烟者轮流抽烟</li>
<li></li>
<li>关系分析 (从事件的角度来分析)</li>
<li>互斥关系: 桌子是容量为1的缓冲区,要互斥访问</li>
<li>同步关系: 1. 桌子上有组合一(纸+胶水)-&gt; 第一个抽烟者取走</li>
<li><pre><code>     2. 桌子上有组合二(烟草+胶水)-&gt; 第二个抽烟者取走
</code></pre>
</li>
<li><pre><code>     3. 桌子上有组合三(烟草+纸)-&gt; 第三个抽烟者取走
</code></pre>
</li>
<li><pre><code>     4. 发出完成信号-&gt;供应者将下一个组合放上
</code></pre>
</li>
<li> *&#x2F;</li>
</ul>
<p>public class 吸烟者问题 {</p>
<pre><code>private int i = 0;  //用于实现轮流抽烟

final Semaphore offer1 = new Semaphore(0);  //组合一资源的量
final Semaphore offer2 = new Semaphore(0);  //组合二资源的量
final Semaphore offer3 = new Semaphore(0);  //组合三资源的量
final Semaphore table = new Semaphore(1);  //缓冲区(桌子)是否收到信号放上资源


public static void main(String[] args) &#123;

    吸烟者问题 test = new 吸烟者问题();

    new Thread(test.new provider()).start();
    new Thread(test.new smoker1()).start();
    new Thread(test.new smoker2()).start();
    new Thread(test.new smoker3()).start();

&#125;

class provider implements Runnable&#123;

    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;
                table.acquire();  //P(finish)
                if (i==0)&#123;
                    Thread.sleep(100);
                    System.out.println(&quot;供应者放上了组合一资源&quot;);
                    offer1.release();
                &#125;else if (i==1)&#123;
                    Thread.sleep(100);
                    System.out.println(&quot;供应者放上了组合二资源&quot;);
                    offer2.release();

                &#125;else if (i==2)&#123;
                    Thread.sleep(100);
                    System.out.println(&quot;供应者放上了组合三资源&quot;);
                    offer3.release();

                &#125;
                i = (i+1)%3;

            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;
        &#125;
    &#125;
&#125;

class smoker1 implements Runnable&#123;
    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;

                offer1.acquire();
                Thread.sleep(100);
                System.out.println(&quot;抽烟者一拿走了材料&quot;);
            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                try &#123;
                    Thread.sleep(300);
                    System.out.println(&quot;抽烟者一卷好了烟&quot;);
                    Thread.sleep(1000);
                    System.out.println(&quot;抽烟者一抽完了烟&quot;);

                &#125; catch (InterruptedException e) &#123;
                    e.printStackTrace();
                &#125;finally &#123;
                    table.release();  //发出完成信号
                &#125;
            &#125;
        &#125;
    &#125;
&#125;


class smoker2 implements Runnable&#123;
    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;
                offer2.acquire();
                Thread.sleep(100);
                System.out.println(&quot;抽烟者二拿走了材料&quot;);
            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                try &#123;
                    Thread.sleep(300);
                    System.out.println(&quot;抽烟者二卷好了烟&quot;);
                    Thread.sleep(1000);
                    System.out.println(&quot;抽烟者二抽完了烟&quot;);

                &#125; catch (InterruptedException e) &#123;
                    e.printStackTrace();
                &#125;finally &#123;
                    table.release();  //发出完成信号
                &#125;
            &#125;
        &#125;
    &#125;
&#125;

class smoker3 implements Runnable&#123;
    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;
                offer3.acquire();
                Thread.sleep(100);
                System.out.println(&quot;抽烟者三拿走了材料&quot;);
            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                try &#123;
                    Thread.sleep(100);
                    System.out.println(&quot;抽烟者三卷好了烟&quot;);
                    Thread.sleep(1000);
                    System.out.println(&quot;抽烟者三抽完了烟&quot;);

                &#125; catch (InterruptedException e) &#123;
                    e.printStackTrace();
                &#125;finally &#123;
                    table.release();  //发出完成信号
                &#125;
            &#125;
        &#125;
    &#125;
&#125;
</code></pre>
<p>}</p>
<h4 id="读者-写者问题"><a href="#读者-写者问题" class="headerlink" title="读者-写者问题"></a>读者-写者问题</h4><p>&#x2F;**</p>
<ul>
<li>有读者写者两组并发进程,共享一个文件,当两个或两个以上的读进程同时访问共享数据时,不会有副作用</li>
<li>若某个写进程和其他进程(读和写)同时访问共享数据时则可能导致数据不一致</li>
<li>因此要求: 1. 允许多个读者同时对文件读</li>
<li><pre><code>      2. 只允许一个写者往文件中写信息
</code></pre>
</li>
<li><pre><code>      3. 任一写者在完成写操作前不允许其他读者或写者工作
</code></pre>
</li>
<li><pre><code>      4. 写者执行操作前,应让已有的读者和写者全部退出
</code></pre>
</li>
<li></li>
<li>关系分析</li>
<li>互斥关系: 写进程-写进程, 写进程-读进程, 但读与读不互斥</li>
<li>写者与任何进程都互斥,设置一个互斥信号量rw,在写者访问前后PV</li>
<li>读者与写者也互斥,因此读者操作前后也要PV</li>
<li>但读者之间不互斥,所以只让第一个读进程”加锁”, 最后一个读进程”解锁”</li>
<li>设置一个count来记录当前有几个读进程在访问</li>
<li></li>
<li>若两个读进程并发执行, 则有可能先后执行P(rw), 从而使第二个阻塞</li>
<li>原因在于对count变量的检查和赋值无法一气呵成</li>
<li>因此要设置mutex保证对count的访问是互斥的</li>
<li></li>
<li>潜在问题: 只要有读进程在读,写进程就要一直阻塞等待,可能”饿死”</li>
<li>增加一个互斥信号量,实现”写优先”</li>
<li> *&#x2F;</li>
</ul>
<p>public class 读者写者问题 {<br>    private static int count &#x3D; 0;    &#x2F;&#x2F;记录当前第几个读进程</p>
<pre><code>private Semaphore rw = new Semaphore(1);     //用于实现对文件互斥访问,表示当前是否有访问
private Semaphore mutex = new Semaphore(1);  //用于保证对count变量的互斥访问
private Semaphore w = new Semaphore(1);      //用于实现&quot;写优先&quot;

public static void main(String[] args) &#123;

    读者写者问题 test = new 读者写者问题();

    new Thread(test.new reader()).start();
    new Thread(test.new writer()).start();
    new Thread(test.new reader()).start();
    new Thread(test.new reader()).start();
    new Thread(test.new reader()).start();
    new Thread(test.new reader()).start();
&#125;

class writer implements Runnable&#123;

    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;
                w.acquire();   // P(w)
                rw.acquire();  // P(rw)  对文件访问加锁
                System.out.println(Thread.currentThread().getName()+&quot;写进程正在写文件&quot;);
                Thread.sleep(100);

            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                System.out.println(Thread.currentThread().getName()+&quot;写进程写完了&quot;);
                rw.release();  //写完后加锁
                w.release();
            &#125;
        &#125;
    &#125;
&#125;

class reader implements Runnable&#123;

    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;
                w.acquire();   // P(w)

                mutex.acquire();  // P(mutex) 各读进程互斥访问count
                if (count == 0)&#123;
                    rw.acquire();  // P(rw)  第一个读进程对文件访问加锁
                &#125;
                count++;
                mutex.release();  // V(mutex)

                w.release();      // V(w)


                System.out.println(Thread.currentThread().getName()+&quot;读进程正在读文件&quot;);
                Thread.sleep(1000);
                System.out.println(Thread.currentThread().getName()+&quot;读进程读完了&quot;);

                mutex.acquire();
                count--;
                if (count==0)&#123;
                    rw.release();  //最后一个读进程负责解锁
                &#125;
                mutex.release();

            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;
        &#125;
    &#125;
&#125;
</code></pre>
<p>}</p>
<p>读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路.<br>其核心思想在于设置一个计数器count用来记录当前正在访问共享文件的读进程数.<br>我们可以用count的值判断当前进入的进程是否是第一个&#x2F;最后一个读进程,从而做出不同的处理<br>另外,对count变量的检查和赋值不能一气呵成导致了一些错误,如果需要实现”一气呵成”,自然应该想到用互斥信号量</p>
<h4 id="哲学家进餐问题"><a href="#哲学家进餐问题" class="headerlink" title="哲学家进餐问题"></a>哲学家进餐问题</h4><p>&#x2F;**</p>
<ul>
<li>一张桌子上五个哲学家,每两个哲学家间摆一根筷子,桌子中间一碗饭. 哲学家只思考与吃饭. 哲学家思考时不影响他人.</li>
<li>只有当哲学家饥饿时,才试图拿左右两根筷子(一根一根拿起). 如果筷子在他人手上则需等待.</li>
<li>只有同时那两根筷子才可以进餐,完毕后继续思考</li>
<li></li>
<li>关系分析</li>
<li>互斥关系: 哲学家与左右邻居对中间的筷子是互斥关系.</li>
<li>如何避免临界资源分配不当造成死锁是该问题的关键</li>
<li></li>
<li>仅当一个哲学家左右两只筷子都可用时才允许他抓起筷子<br> *&#x2F;</li>
</ul>
<p>如果5个人同时拿起一只筷子,则造成”死锁”<br>如何防止死锁</p>
<ol>
<li>可以对哲学家进程施加限制,比如最多允许4个哲学家同时进餐.<br> 这样至少有一个人可以拿两只</li>
<li>要求奇数号先左后右,偶数号相反<br>这就保证相邻两人只有一人会拿起一只筷子,另一个直接阻塞,就避免了占用一只后再等待另一只的情况</li>
<li>仅当一个哲学家左右两只筷子都可用时才允许他抓起筷子</li>
</ol>
<p>public class 哲学家进餐 {</p>
<pre><code>Semaphore[] chopsticks = &#123;new Semaphore(1),new Semaphore(1),new Semaphore(1),new Semaphore(1),new Semaphore(1)&#125;;
Semaphore mutex = new Semaphore(1); //互斥的取筷子

public static void main(String[] args) &#123;

    哲学家进餐 test = new 哲学家进餐();

    new Thread(test.new p0()).start();
    new Thread(test.new p1()).start();
    new Thread(test.new p2()).start();
    new Thread(test.new p3()).start();
    new Thread(test.new p4()).start();
&#125;

class p0 implements Runnable&#123;

    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;
                mutex.acquire();
                chopsticks[0].acquire();   //拿左筷子
                chopsticks[(0+1)%5].acquire();  //拿右筷子
                mutex.release();

                System.out.println(&quot;哲学家0正在吃饭&quot;);
                Thread.sleep(1000);
                System.out.println(&quot;哲学家0继续思考&quot;);

            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                chopsticks[0].release();  //放下左筷子
                chopsticks[(0+1)%5].release();  //放下右筷子

            &#125;

        &#125;
    &#125;
&#125;

class p1 implements Runnable&#123;

    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;
                mutex.acquire();
                chopsticks[1].acquire();   //拿左筷子
                chopsticks[(1+1)%5].acquire();  //拿右筷子
                mutex.release();

                System.out.println(&quot;哲学家1正在吃饭&quot;);
                Thread.sleep(1000);
                System.out.println(&quot;哲学家1继续思考&quot;);

            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                chopsticks[1].release();  //放下左筷子
                chopsticks[(1+1)%5].release();  //放下右筷子
            &#125;

        &#125;
    &#125;
&#125;

class p2 implements Runnable&#123;

    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;
                mutex.acquire();
                chopsticks[2].acquire();   //拿左筷子
                chopsticks[(2+1)%5].acquire();  //拿右筷子
                mutex.release();

                System.out.println(&quot;哲学家2正在吃饭&quot;);
                Thread.sleep(1000);
                System.out.println(&quot;哲学家2继续思考&quot;);

            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                chopsticks[2].release();  //放下左筷子
                chopsticks[(2+1)%5].release();  //放下右筷子
            &#125;

        &#125;
    &#125;
&#125;

class p3 implements Runnable&#123;

    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;
                mutex.acquire();
                chopsticks[3].acquire();   //拿左筷子
                chopsticks[(3+1)%5].acquire();  //拿右筷子
                mutex.release();

                System.out.println(&quot;哲学家3正在吃饭&quot;);
                Thread.sleep(1000);
                System.out.println(&quot;哲学家3继续思考&quot;);

            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                chopsticks[3].release();  //放下左筷子
                chopsticks[(3+1)%5].release();  //放下右筷子
            &#125;

        &#125;
    &#125;
&#125;

class p4 implements Runnable&#123;

    @Override
    public void run() &#123;
        while (true)&#123;
            try &#123;
                mutex.acquire();
                chopsticks[4].acquire();   //拿左筷子
                chopsticks[(4+1)%5].acquire();  //拿右筷子
                mutex.release();

                System.out.println(&quot;哲学家4正在吃饭&quot;);
                Thread.sleep(1000);
                System.out.println(&quot;哲学家4继续思考&quot;);

            &#125; catch (InterruptedException e) &#123;
                e.printStackTrace();
            &#125;finally &#123;
                chopsticks[4].release();  //放下左筷子
                chopsticks[(4+1)%5].release();  //放下右筷子
            &#125;

        &#125;
    &#125;
&#125;
</code></pre>
<p>}</p>
<p>哲学家进餐问题的关键在于解决进程死锁问题的隐患<br>这些进程之间只存在互斥关系,但是与之前接触到的互斥关系不同的是,每个进程都需要同时持有两个临界资源<br>,因此就有死锁问题的隐患</p>
<h3 id="管程"><a href="#管程" class="headerlink" title="管程"></a>管程</h3><p>信号量机制存在的问题: 编写程序困难,易出错,引入”管程”,一种高级同步机制</p>
<p>定义: 管程是一种特殊的软件模块<br>由以下组成</p>
<ol>
<li>局部于管程的共享数据结构说明</li>
<li>对该数据结构进行操作的一组过程</li>
<li>对局部于管程的共享数据设置初始值的语句</li>
<li>管程有一个名字</li>
</ol>
<p>管程的基本特征:</p>
<ol>
<li>局部于管程的数据只能被局部于管程的过程所访问</li>
<li>一个进程只有通过调用管程内的过程才能进入管程访问共享数据</li>
<li>每次仅允许一个进程在管程内执行某个内部过程</li>
</ol>
<p>管程就像把PV操作当作语句封装成函数,这些函数又被封装在管程中</p>
<p>Java中类似于管程的机制<br>用synchronized关键字描述一个函数,则该函数同一时间段只能被一个线程调用</p>
<p>public class 多线程案例 {</p>
<pre><code>public static void main(String[] args)&#123;
    //创建包子对象
    多线程案例.BaoZi bz = new 多线程案例.BaoZi();
    //创建包子铺线程,开始生产包子
    new 多线程案例.BaoZiPu(bz).start();
    //创建顾客线程,开始吃包子
    new 多线程案例.ChiHuo(bz).start();
&#125;

static class BaoZi &#123;
    //皮
    String pi;
    //馅
    String xian;
    //包子的状态
    boolean flag = false;
&#125;

static class BaoZiPu extends Thread&#123;
    private BaoZi bz;

    public BaoZiPu(BaoZi bz) &#123;
        this.bz = bz;
    &#125;

    //设置线程生产包子
    @Override
    public void run() &#123;
        int count = 0;
        //让包子一直生产到100个包子
        while(count&lt;100)&#123;
            //同步技术
            synchronized (bz)&#123;
                if(bz.flag == true)&#123;
                    //包子铺调用wait方法进入等待状态
                    try &#123;
                        bz.wait();
                    &#125; catch (InterruptedException e) &#123;
                        e.printStackTrace();
                    &#125;
                &#125;
                //被唤醒后生产包子
                //交替生产两种包子
                if(count%2 == 0)&#123;
                    //生产薄皮三鲜馅儿
                    bz.pi = &quot;薄皮&quot;;
                    bz.xian = &quot;三鲜馅儿&quot;;
                &#125;else&#123;
                    //生产冰皮牛肉大葱馅儿
                    bz.pi = &quot;冰皮&quot;;
                    bz.xian = &quot;牛肉大葱馅儿&quot;;
                &#125;
                count++;

                System.out.println(&quot;包子铺正在做&quot;+bz.pi+bz.xian+&quot;的包子&quot;);
                //做一个包子五秒钟
                try &#123;
                    Thread.sleep(5000);
                &#125; catch (InterruptedException e) &#123;
                    e.printStackTrace();
                &#125;
                //做好包子,flag改成有
                bz.flag = true;
                bz.notify();
                System.out.println(&quot;包子铺做好了&quot;+bz.pi+bz.xian+&quot;的包子&quot;);
            &#125;

        &#125;
    &#125;
&#125;

static class ChiHuo extends Thread &#123;
    private BaoZi bz;

    public ChiHuo(BaoZi bz) &#123;
        this.bz = bz;
    &#125;

    @Override
    public void run() &#123;
        int count=0;
        while(count&lt;100)&#123;
            synchronized (bz)&#123;
                if(bz.flag == false)&#123;
                    try &#123;
                        bz.wait();
                    &#125; catch (InterruptedException e) &#123;
                        e.printStackTrace();
                    &#125;
                &#125;

                //被唤醒后吃包子
                System.out.println(&quot;顾客在吃&quot;+bz.pi+bz.xian+&quot;的包子&quot;);
                try &#123;
                    Thread.sleep(3000);
                &#125; catch (InterruptedException e) &#123;
                    e.printStackTrace();
                &#125;
                //吃完包子修改状态为没有
                bz.flag = false;
                count++;
                //唤醒包子铺继续生产
                bz.notify();
                System.out.println(&quot;顾客把&quot;+bz.pi+bz.xian+&quot;的包子吃完了&quot;);
                System.out.println(&quot;--------------------------------------&quot;);
            &#125;
        &#125;
    &#125;
&#125;
</code></pre>
<p>}</p>
<h3 id="死锁"><a href="#死锁" class="headerlink" title="死锁"></a>死锁</h3><p>在并发环境下,各进程因竞争资源而造成的一种互相等待对方手里的资源,导致进程都阻塞,都无法向前推进的现象</p>
<p>死锁,饥饿,死循环的区别<br>饥饿: 长期得不到想要的资源,某进程无法向前推进的现象<br>死循环: 某进程执行过程中一直跳不出某个循环的现象</p>
<p>死锁至少两个或两个以上的进程同时发生<br>饥饿可能只有一个进程<br>死锁和饥饿是管理者(操作系统的问题),死循环是被管理者(程序)的问题</p>
<p>死锁产生的必要条件:<br>    1. 互斥条件: 只有对必须互斥使用的资源的争抢才会导致死锁<br>    2. 不剥夺条件: 进程所获得的资源在未使用完之前,不能由其他进程强行夺走,只能主动释放<br>    3. 请求和保持条件: 进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已被占有<br>    4. 循环等待条件: 存在一种进程资源的循环等待链, 链中每一个进程已得资源同时被下一进程请求</p>
<pre><code>注: 发生死锁一定有循环等待,但循环等待不一定死锁
</code></pre>
<h3 id="死锁的处理"><a href="#死锁的处理" class="headerlink" title="死锁的处理"></a>死锁的处理</h3><p>预防死锁: 破坏四个必要条件之一或几个<br>避免死锁: 用某种方法防止系统进入不安全状态(银行家算法)<br>死锁的检测和解除: 允许死锁的发生,然后采取某种措施接触死锁</p>
<ol>
<li><p>预防死锁</p>
<ol>
<li>破坏互斥<br> 把只能互斥使用的资源改造成允许共享使用<br> Spoling技术, 吧独占设备在逻辑上改造成共享设备</li>
<li>破坏不剥夺<br> 方案一: 当某进程请求资源得不到满足时,必须立即释放<br> 可能导致饥饿<br> 方案二: 由操作系统协助强行剥夺<br> 反复申请释放,增大了开销</li>
<li>破环请求和保持条件<br> 采用静态分配方法,即进程一次申请所需全部资源,在资源未满足前不让他投入运行<br> 投入运行后这些资源一直归他所有,不会再请求别的资源<br> 资源利用率极低,且可能导致饥饿</li>
<li>破坏循环等待<br> 采用顺序资源分配法,首先给系统中的资源编号,规定每个进程必须按编号递增的顺序请求资源<br> 同类资源(即编号相同的资源)一次申请完<br> 原理: 一个进程只有占有小编号的资源是，才有资格申请更大编号的资源。<br>   按此规则，以持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象<br><br> 不方便新增设备,可能重新分配所有的编号<br> 进程实际使用资源可能和编号递增顺序不一致,导致资源浪费<br> 必须按规定次序申请资源,用户编程麻烦</li>
</ol>
</li>
<li><p>避免死锁<br> 安全序列:<br> 指如果系统按照某种序列分配资源,则每个进程都能顺利完成.<br> 只要找出一个安全序列,系统就是安全状态,安全序列可能有多个<br> 安全状态一定不会死锁,不安全状态可能会死锁</p>
<p> 银行家算法<br> 核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂不答应这次请求<br>           让该进程先阻塞等待<br> 实例：银行家手里有100亿<br>   B厂最多会借70亿<br>   A厂最多会借40亿<br>   T厂最多会借50亿<br>   如果借给企业总数达不到企业提出的最大要求，钱就拿不回来<br> 最大需求    已借走   最多还会借<br> B      70         20         50<br> A      40         10         30<br> T      50         30         20</p>
<p> 银行家算法步骤</p>
<ol>
<li>检查此次申请是否超过了之前声明的最大需求数</li>
<li>检查此时系统剩余的可用资源是否还能满足这次请求</li>
<li>试探着分配，更改各数据结构</li>
<li>用安全性算法检查此次分配是否会导致系统进入不安全状态</li>
</ol>
<p> 安全性算法步骤<br> 检查当前的剩余可用资源是否满足某个进程的最大需求<br> 如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收<br> 不断重复上述过程，看最终是否能让所有进程加入安全序列</p>
</li>
</ol>
<p>public class 银行家算法 {</p>
<pre><code>int[] Available = &#123;10, 8, 7&#125;;
int[][] Max = new int[3][3];
int[][] Alloction = new int[3][3];
int[][] Need = new int[3][3];
int[][] Request = new int[3][3];
int[] Work = new int[3];

int num = 0;//进程编号
Scanner in = new Scanner(System.in);

public 银行家算法() &#123;
    // Max=&#123;&#123;6,3,2&#125;,&#123;5,6,1&#125;,&#123;2,3,2&#125;&#125;;

&#125;

public void setSystemVariable()&#123;//设置各初始系统变量，并判断是否处于安全状态。
    setMax();
    setAlloction();
    printSystemVariable();
    SecurityAlgorithm();
&#125;

public void setMax() &#123;//设置Max矩阵
    System.out.println(&quot;请设置各进程的最大需求矩阵Max：&quot;);
    for (int i = 0; i &lt; 3; i++) &#123;
        System.out.println(&quot;请输入进程P&quot; + i + &quot;的最大资源需求量：&quot;);
        for (int j = 0; j &lt; 3; j++) &#123;
            Max[i][j] = in.nextInt();
        &#125;
    &#125;
&#125;

public void setAlloction() &#123;//设置已分配矩阵Alloction
    System.out.println(&quot;请设置请各进程分配矩阵Alloction：&quot;);
    for (int i = 0; i &lt; 3; i++) &#123;
        System.out.println(&quot;晴输入进程P&quot; + i + &quot;的分配资源量：&quot;);
        for (int j = 0; j &lt; 3; j++) &#123;
            Alloction[i][j] = in.nextInt();
        &#125;
    &#125;
    System.out.println(&quot;Available=Available-Alloction.&quot;);
    System.out.println(&quot;Need=Max-Alloction.&quot;);
    for (int i = 0; i &lt; 3; i++) &#123;//设置Alloction矩阵
        for (int j = 0; j &lt; 3; j++) &#123;
            Available[i] = Available[i] - Alloction[j][i];
        &#125;
    &#125;
    for (int i = 0; i &lt; 3; i++) &#123;//设置Need矩阵
        for (int j = 0; j &lt; 3; j++) &#123;
            Need[i][j] = Max[i][j] - Alloction[i][j];
        &#125;
    &#125;
&#125;

public void printSystemVariable()&#123;
    System.out.println(&quot;此时资源分配量如下：&quot;);
    System.out.println(&quot;进程  &quot;+&quot;   Max   &quot;+&quot;   Alloction &quot;+&quot;    Need  &quot;+&quot;     Available &quot;);
    for(int i=0;i&lt;3;i++)&#123;
        System.out.print(&quot;P&quot;+i+&quot;  &quot;);
        for(int j=0;j&lt;3;j++)&#123;
            System.out.print(Max[i][j]+&quot;  &quot;);
        &#125;
        System.out.print(&quot;|  &quot;);
        for(int j=0;j&lt;3;j++)&#123;
            System.out.print(Alloction[i][j]+&quot;  &quot;);
        &#125;
        System.out.print(&quot;|  &quot;);
        for(int j=0;j&lt;3;j++)&#123;
            System.out.print(Need[i][j]+&quot;  &quot;);
        &#125;
        System.out.print(&quot;|  &quot;);
        if(i==0)&#123;
            for(int j=0;j&lt;3;j++)&#123;
                System.out.print(Available[j]+&quot;  &quot;);
            &#125;
        &#125;
        System.out.println();
    &#125;
&#125;

public void setRequest() &#123;//设置请求资源量Request


    System.out.println(&quot;请输入请求资源的进程编号：&quot;);
    num= in.nextInt();//设置全局变量进程编号num
    System.out.println(&quot;请输入请求各资源的数量：&quot;);
    for (int j = 0; j &lt; 3; j++) &#123;
        Request[num][j] = in.nextInt();
    &#125;
    System.out.println(&quot;即进程P&quot; + num + &quot;对各资源请求Request：(&quot; + Request[num][0] + &quot;,&quot; + Request[num][1] + &quot;,&quot; + Request[num][2] + &quot;).&quot;);

    BankerAlgorithm();
&#125;

public void BankerAlgorithm() &#123;//银行家算法
    boolean T=true;

    if (Request[num][0] &lt;= Need[num][0] &amp;&amp; Request[num][1] &lt;= Need[num][1] &amp;&amp; Request[num][2] &lt;= Need[num][2]) &#123;//判断Request是否小于Need
        if (Request[num][0] &lt;= Available[0] &amp;&amp; Request[num][1] &lt;= Available[1] &amp;&amp; Request[num][2] &lt;= Available[2]) &#123;//判断Request是否小于Alloction
            for (int i = 0; i &lt; 3; i++) &#123;
                Available[i] -= Request[num][i];
                Alloction[num][i] += Request[num][i];
                Need[num][i] -= Request[num][i];
            &#125;

        &#125; else &#123;
            System.out.println(&quot;当前没有足够的资源可分配，进程P&quot; + num + &quot;需等待。&quot;);
            T=false;
        &#125;
    &#125; else &#123;
        System.out.println(&quot;进程P&quot; + num + &quot;请求已经超出最大需求量Need.&quot;);
        T=false;
    &#125;

    if(T==true)&#123;
        printSystemVariable();
        System.out.println(&quot;现在进入安全算法：&quot;);
        SecurityAlgorithm();
    &#125;
&#125;


public void SecurityAlgorithm() &#123;//安全算法
    boolean[] Finish = &#123;false, false, false&#125;;//初始化Finish
    int count = 0;//完成进程数
    int circle=0;//循环圈数
    int[] S=new int[3];//安全序列
    for (int i = 0; i &lt; 3; i++) &#123;//设置工作向量
        Work[i] = Available[i];
    &#125;
    boolean flag = true;
    while (count &lt; 3) &#123;
        if(flag)&#123;
            System.out.println(&quot;进程  &quot;+&quot;   Work  &quot;+&quot;   Alloction &quot;+&quot;    Need  &quot;+&quot;     Work+Alloction &quot;);
            flag = false;
        &#125;
        for (int i = 0; i &lt; 3; i++) &#123;

            if (Finish[i]==false&amp;&amp;Need[i][0]&lt;=Work[0]&amp;&amp;Need[i][1]&lt;=Work[1]&amp;&amp;Need[i][2]&lt;=Work[2]) &#123;//判断条件
                System.out.print(&quot;P&quot;+i+&quot;  &quot;);
                for (int k = 0; k &lt; 3; k++)&#123;
                    System.out.print(Work[k]+&quot;  &quot;);
                &#125;
                System.out.print(&quot;|  &quot;);
                for (int j = 0; j&lt;3;j++)&#123;
                    Work[j]+=Alloction[i][j];
                &#125;
                Finish[i]=true;//当当前进程能满足时
                S[count]=i;//设置当前序列排号

                count++;//满足进程数加1
                for(int j=0;j&lt;3;j++)&#123;
                    System.out.print(Alloction[i][j]+&quot;  &quot;);
                &#125;
                System.out.print(&quot;|  &quot;);
                for(int j=0;j&lt;3;j++)&#123;
                    System.out.print(Need[i][j]+&quot;  &quot;);
                &#125;
                System.out.print(&quot;|  &quot;);
                for(int j=0;j&lt;3;j++)&#123;
                    System.out.print(Work[j]+&quot;  &quot;);
                &#125;
                System.out.println();
            &#125;

        &#125;
        circle++;//循环圈数加1

        if(count==3)&#123;//判断是否满足所有进程需要
            System.out.print(&quot;此时存在一个安全序列：&quot;);
            for (int i = 0; i&lt;3;i++)&#123;//输出安全序列
                System.out.print(&quot;P&quot;+S[i]+&quot; &quot;);
            &#125;
            System.out.println(&quot;故当前可分配！&quot;);
            break;//跳出循环
        &#125;
        if(count&lt;circle)&#123;//判断完成进程数是否小于循环圈数
            count=5;
            System.out.println(&quot;当前系统处于不安全状态，故不存在安全序列。&quot;);
            break;//跳出循环
        &#125;
    &#125;
&#125;
</code></pre>
<p>}</p>
<ol start="3">
<li><p>检测和解除<br> 为了能对系统是否已发生了死锁进行检测，必须：</p>
<ol>
<li>用资源分配图来保存资源的请求和分配信息</li>
<li>提供了一种算法，利用上述信息来检测系统是否已进入死锁状态</li>
</ol>
<p> 资源分配图：<br>     两种节点：<br>         进程节点：对应一个进程<br>         资源节点：对应一类资源，一类资源可能有多个<br>     两种边：<br>         进程节点-&gt;资源节点: 表示进程想申请几个资源,每条边代表一个<br>         资源节点-&gt;进程节点: 表示已经为进程分配了几个资源,每条边代表一个<br> 一般用矩形表示资源节点,矩形中的圆代表资源<br> 稀疏图用邻接表表示, 稠密图用邻接矩阵</p>
<p> 检测死锁的算法</p>
<ol>
<li>在图中找出既不阻塞也不是孤点的进程pi(即找出一条有向边与它相连,<br>且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量),<br>有足够的空闲资源使该进程完成,消去该进程的边,释放资源</li>
<li>释放资源可以唤醒某些阻塞的进程,重复操作</li>
</ol>
<p> 若最终能消除所有边,就称这个图可以完全简化,此时一定没有死锁,否则就发生了死锁</p>
<p> 死锁的解除:<br> 一旦检测出死锁的发生,就应该立即解除死锁. 并不是系统中所有进程的死锁状态,<br> 用死锁检测算法化简图后还连着边的进程就是死锁进程</p>
<ol>
<li>资源剥夺法<br> 挂起某些死锁进程,并抢占他的资源<br> 但要防止被挂起后饥饿</li>
<li>撤销进程法(终止进程法)<br> 强制撤销部分,甚至全部死锁进程,并剥夺资源<br> 实现简单,但付出代价很大,可能已经运行快结束了,也要从头再来</li>
<li>进程回退法<br> 让一个或多个死锁进程回退到足以避免死锁的地步</li>
</ol>
<p> 决定对哪个进程动手</p>
<ol>
<li>进程优先级 低的先剥夺</li>
<li>已执行多长时间 短的先</li>
<li>还要多久完成 长的先</li>
<li>进程已经使用了多少资源 劫富济贫</li>
<li>进程是交互式的还是批处理式 优先杀批处理式的</li>
</ol>
</li>
</ol>

                
            </div>
            <hr/>

            

    <div class="reprint" id="reprint-statement">
        
            <div class="reprint__author">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-user">
                        文章作者:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="/shiqing/about" rel="external nofollow noreferrer">世庆</a>
                </span>
            </div>
            <div class="reprint__type">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-link">
                        文章链接:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="https://shiqing.gitee.io/shiqing/2021/05/10/cao-zuo-xi-tong/cao-zuo-xi-tong-di-er-zhang/">https://shiqing.gitee.io/shiqing/2021/05/10/cao-zuo-xi-tong/cao-zuo-xi-tong-di-er-zhang/</a>
                </span>
            </div>
            <div class="reprint__notice">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-copyright">
                        版权声明:
                    </i>
                </span>
                <span class="reprint-info">
                    本博客所有文章除特別声明外，均采用
                    <a href="https://creativecommons.org/licenses/by/4.0/deed.zh" rel="external nofollow noreferrer" target="_blank">CC BY 4.0</a>
                    许可协议。转载请注明来源
                    <a href="/shiqing/about" target="_blank">世庆</a>
                    !
                </span>
            </div>
        
    </div>

    <script async defer>
      document.addEventListener("copy", function (e) {
        let toastHTML = '<span>复制成功，请遵循本文的转载规则</span><button class="btn-flat toast-action" onclick="navToReprintStatement()" style="font-size: smaller">查看</a>';
        M.toast({html: toastHTML})
      });

      function navToReprintStatement() {
        $("html, body").animate({scrollTop: $("#reprint-statement").offset().top - 80}, 800);
      }
    </script>



            <div class="tag_share" style="display: block;">
                <div class="post-meta__tag-list" style="display: inline-block;">
                    
                        <div class="article-tag">
                            
                                <a href="/shiqing/tags/%E8%BF%9B%E7%A8%8B/">
                                    <span class="chip bg-color">进程</span>
                                </a>
                            
                        </div>
                    
                </div>
                <div class="post_share" style="zoom: 80%; width: fit-content; display: inline-block; float: right; margin: -0.15rem 0;">
                    <link rel="stylesheet" type="text/css" href="/shiqing/libs/share/css/share.min.css">
<div id="article-share">

    
    <div class="social-share" data-sites="twitter,facebook,google,qq,qzone,wechat,weibo,douban,linkedin" data-wechat-qrcode-helper="<p>微信扫一扫即可分享！</p>"></div>
    <script src="/shiqing/libs/share/js/social-share.min.js"></script>
    

    

</div>

                </div>
            </div>
            
                <style>
    #reward {
        margin: 40px 0;
        text-align: center;
    }

    #reward .reward-link {
        font-size: 1.4rem;
        line-height: 38px;
    }

    #reward .btn-floating:hover {
        box-shadow: 0 6px 12px rgba(0, 0, 0, 0.2), 0 5px 15px rgba(0, 0, 0, 0.2);
    }

    #rewardModal {
        width: 320px;
        height: 350px;
    }

    #rewardModal .reward-title {
        margin: 15px auto;
        padding-bottom: 5px;
    }

    #rewardModal .modal-content {
        padding: 10px;
    }

    #rewardModal .close {
        position: absolute;
        right: 15px;
        top: 15px;
        color: rgba(0, 0, 0, 0.5);
        font-size: 1.3rem;
        line-height: 20px;
        cursor: pointer;
    }

    #rewardModal .close:hover {
        color: #ef5350;
        transform: scale(1.3);
        -moz-transform:scale(1.3);
        -webkit-transform:scale(1.3);
        -o-transform:scale(1.3);
    }

    #rewardModal .reward-tabs {
        margin: 0 auto;
        width: 210px;
    }

    .reward-tabs .tabs {
        height: 38px;
        margin: 10px auto;
        padding-left: 0;
    }

    .reward-content ul {
        padding-left: 0 !important;
    }

    .reward-tabs .tabs .tab {
        height: 38px;
        line-height: 38px;
    }

    .reward-tabs .tab a {
        color: #fff;
        background-color: #ccc;
    }

    .reward-tabs .tab a:hover {
        background-color: #ccc;
        color: #fff;
    }

    .reward-tabs .wechat-tab .active {
        color: #fff !important;
        background-color: #22AB38 !important;
    }

    .reward-tabs .alipay-tab .active {
        color: #fff !important;
        background-color: #019FE8 !important;
    }

    .reward-tabs .reward-img {
        width: 210px;
        height: 210px;
    }
</style>

<div id="reward">
    <a href="#rewardModal" class="reward-link modal-trigger btn-floating btn-medium waves-effect waves-light red">赏</a>

    <!-- Modal Structure -->
    <div id="rewardModal" class="modal">
        <div class="modal-content">
            <a class="close modal-close"><i class="fas fa-times"></i></a>
            <h4 class="reward-title">你的赏识是我前进的动力</h4>
            <div class="reward-content">
                <div class="reward-tabs">
                    <ul class="tabs row">
                        <li class="tab col s6 alipay-tab waves-effect waves-light"><a href="#alipay">支付宝</a></li>
                        <li class="tab col s6 wechat-tab waves-effect waves-light"><a href="#wechat">微 信</a></li>
                    </ul>
                    <div id="alipay">
                        <img src="/shiqing/medias/reward/alipay.jpg" class="reward-img" alt="支付宝打赏二维码">
                    </div>
                    <div id="wechat">
                        <img src="/shiqing/medias/reward/wechat.png" class="reward-img" alt="微信打赏二维码">
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>

<script>
    $(function () {
        $('.tabs').tabs();
    });
</script>

            
        </div>
    </div>

    

    

    

    

    

    

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="fas fa-chevron-left"></i>&nbsp;上一篇</div>
            <div class="card">
                <a href="/shiqing/2021/05/24/cao-zuo-xi-tong/cao-zuo-xi-tong-di-san-zhang/">
                    <div class="card-image">
                        
                        
                        <img src="/shiqing/medias/featureimages/0.jpg" class="responsive-img" alt="操作系统第三章">
                        
                        <span class="card-title">操作系统第三章</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            
                        
                    </div>
                    <div class="publish-info">
                        <span class="publish-date">
                            <i class="far fa-clock fa-fw icon-date"></i>2021-05-24
                        </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/shiqing/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" class="post-category">
                                    操作系统
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/shiqing/tags/%E5%86%85%E5%AD%98/">
                        <span class="chip bg-color">内存</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                下一篇&nbsp;<i class="fas fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="/shiqing/2021/04/29/cao-zuo-xi-tong/cao-zuo-xi-tong-di-yi-zhang/">
                    <div class="card-image">
                        
                        
                        <img src="/shiqing/medias/featureimages/15.jpg" class="responsive-img" alt="操作系统第一章">
                        
                        <span class="card-title">操作系统第一章</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="far fa-clock fa-fw icon-date"></i>2021-04-29
                            </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/shiqing/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" class="post-category">
                                    操作系统
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/shiqing/tags/%E6%A6%82%E8%BF%B0/">
                        <span class="chip bg-color">概述</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>

</div>



<!-- 代码块功能依赖 -->
<script type="text/javascript" src="/shiqing/libs/codeBlock/codeBlockFuction.js"></script>

<!-- 代码语言 -->

<script type="text/javascript" src="/shiqing/libs/codeBlock/codeLang.js"></script>


<!-- 代码块复制 -->

<script type="text/javascript" src="/shiqing/libs/codeBlock/codeCopy.js"></script>


<!-- 代码块收缩 -->

<script type="text/javascript" src="/shiqing/libs/codeBlock/codeShrink.js"></script>


    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget card" style="background-color: white;">
            <div class="toc-title"><i class="far fa-list-alt"></i>&nbsp;&nbsp;目录</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fas fa-list-ul"></i>
    </a>
</div>


<script src="/shiqing/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            collapseDepth: Number('0'),
            headingSelector: 'h2, h3, h4'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h2, h3, h4').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).hide();
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).show();
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>

    

</main>




        <footer class="page-footer bg-color">
    
    <div class="container row center-align" style="margin-bottom: 0px !important;">
        <div class="col s12 m8 l8 copy-right">
            Copyright&nbsp;&copy;
            
                <span id="year">2019-2024</span>
            
            <span id="year">2019</span>
            <a href="/shiqing/about" target="_blank">ShiQing</a>
            |&nbsp;Powered by&nbsp;<a href="https://hexo.io/" target="_blank">Hexo</a>
            |&nbsp;Theme&nbsp;<a href="https://github.com/blinkfox/hexo-theme-matery" target="_blank">Matery</a>
            <br>
            
            
            
            
            
            
            <span id="busuanzi_container_site_pv">
                |&nbsp;<i class="far fa-eye"></i>&nbsp;总访问量:&nbsp;<span id="busuanzi_value_site_pv"
                    class="white-color"></span>&nbsp;次
            </span>
            
            
            <span id="busuanzi_container_site_uv">
                |&nbsp;<i class="fas fa-users"></i>&nbsp;总访问人数:&nbsp;<span id="busuanzi_value_site_uv"
                    class="white-color"></span>&nbsp;人
            </span>
            
            <br>
            
            <br>
            
        </div>
        <div class="col s12 m4 l4 social-link social-statis">
    <a href="https://github.com/blinkfox" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fab fa-github"></i>
    </a>



    <a href="mailto:2528393970@qq.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fas fa-envelope-open"></i>
    </a>



    <a href="tencent://AddContact/?fromId=50&fromSubId=1&subcmd=all&uin=2528393970" class="tooltipped" target="_blank" data-tooltip="QQ联系我: 2528393970" data-position="top" data-delay="50">
        <i class="fab fa-qq"></i>
    </a>







    <a href="/shiqing/atom.xml" class="tooltipped" target="_blank" data-tooltip="RSS 订阅" data-position="top" data-delay="50">
        <i class="fas fa-rss"></i>
    </a>

</div>
    </div>
</footer>

<div class="progress-bar"></div>


        <!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fas fa-search"></i>&nbsp;&nbsp;搜索</span>
            <input type="search" id="searchInput" name="s" placeholder="请输入搜索的关键字"
                   class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script type="text/javascript">
$(function () {
    var searchFunc = function (path, search_id, content_id) {
        'use strict';
        $.ajax({
            url: path,
            dataType: "xml",
            success: function (xmlResponse) {
                // get the contents from search data
                var datas = $("entry", xmlResponse).map(function () {
                    return {
                        title: $("title", this).text(),
                        content: $("content", this).text(),
                        url: $("url", this).text()
                    };
                }).get();
                var $input = document.getElementById(search_id);
                var $resultContent = document.getElementById(content_id);
                $input.addEventListener('input', function () {
                    var str = '<ul class=\"search-result-list\">';
                    var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                    $resultContent.innerHTML = "";
                    if (this.value.trim().length <= 0) {
                        return;
                    }
                    // perform local searching
                    datas.forEach(function (data) {
                        var isMatch = true;
                        var data_title = data.title.trim().toLowerCase();
                        var data_content = data.content.trim().replace(/<[^>]+>/g, "").toLowerCase();
                        var data_url = data.url;
                        data_url = data_url.indexOf('/') === 0 ? data.url : '/' + data_url;
                        var index_title = -1;
                        var index_content = -1;
                        var first_occur = -1;
                        // only match artiles with not empty titles and contents
                        if (data_title !== '' && data_content !== '') {
                            keywords.forEach(function (keyword, i) {
                                index_title = data_title.indexOf(keyword);
                                index_content = data_content.indexOf(keyword);
                                if (index_title < 0 && index_content < 0) {
                                    isMatch = false;
                                } else {
                                    if (index_content < 0) {
                                        index_content = 0;
                                    }
                                    if (i === 0) {
                                        first_occur = index_content;
                                    }
                                }
                            });
                        }
                        // show search results
                        if (isMatch) {
                            str += "<li><a href='" + data_url + "' class='search-result-title'>" + data_title + "</a>";
                            var content = data.content.trim().replace(/<[^>]+>/g, "");
                            if (first_occur >= 0) {
                                // cut out 100 characters
                                var start = first_occur - 20;
                                var end = first_occur + 80;
                                if (start < 0) {
                                    start = 0;
                                }
                                if (start === 0) {
                                    end = 100;
                                }
                                if (end > content.length) {
                                    end = content.length;
                                }
                                var match_content = content.substr(start, end);
                                // highlight all keywords
                                keywords.forEach(function (keyword) {
                                    var regS = new RegExp(keyword, "gi");
                                    match_content = match_content.replace(regS, "<em class=\"search-keyword\">" + keyword + "</em>");
                                });

                                str += "<p class=\"search-result\">" + match_content + "...</p>"
                            }
                            str += "</li>";
                        }
                    });
                    str += "</ul>";
                    $resultContent.innerHTML = str;
                });
            }
        });
    };

    searchFunc('/shiqing/search.xml', 'searchInput', 'searchResult');
});
</script>

        <!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fas fa-arrow-up"></i>
    </a>
</div>


        <script src="/shiqing/libs/materialize/materialize.min.js"></script>
        <script src="/shiqing/libs/masonry/masonry.pkgd.min.js"></script>
        <script src="/shiqing/libs/aos/aos.js"></script>
        <script src="/shiqing/libs/scrollprogress/scrollProgress.min.js"></script>
        <script src="/shiqing/libs/lightGallery/js/lightgallery-all.min.js"></script>
        <script src="/shiqing/js/matery.js"></script>

        <!-- Baidu Analytics -->

        <!-- Baidu Push -->

<script>
    (function () {
        var bp = document.createElement('script');
        var curProtocol = window.location.protocol.split(':')[0];
        if (curProtocol === 'https') {
            bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
        } else {
            bp.src = 'http://push.zhanzhang.baidu.com/push.js';
        }
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(bp, s);
    })();
</script>

        
        <script src="/shiqing/libs/others/clicklove.js" async="async"></script>
        
        
        <script async src="/shiqing/libs/others/busuanzi.pure.mini.js"></script>
        

        <script type="text/javascript">
            var OriginTitile = document.title,
                st;
            document.addEventListener("visibilitychange", function () {
                document.hidden ? (document.title = "看不见我~看不见我~", clearTimeout(st)) : (document.title =
                    "(๑•̀ㅂ•́) ✧被发现了～", st = setTimeout(function () {
                        document.title = OriginTitile
                    }, 3e3))
            })
        </script>

        <!-- 背景樱花飘落特效 -->
        
            <script type="text/javascript">
                //只在桌面版网页启用特效
                var windowWidth = $(window).width();
                if (windowWidth > 768) {
                    document.write('<script type="text/javascript" src="/js/xuehuapiaoluo.js"><\/script>');
                }
            </script>
        

        

        


        
        

        

        

        
        <script src="/shiqing/libs/instantpage/instantpage.js" type="module"></script>
        

    </body>

</html>
